「Solution」[BJOI2012]连连看

顺带练习 $dij + EK$ 求费用流

$\mathcal{Link}$

link

$\mathcal{Sol}$

这种两两配对的题盲猜是二分图。
但事实证明是这道题只在 $1≤a,b≤1000$ 的情况下成立。。。

可是并不妨碍做题。

看到分数最大考虑把它转化为一个费用流解决的问题，那么先拆点，从源向每个数的入点连边，从每个数的出点向汇点连边，容量为 $1$，费用为 $0$， 如果两两点之间可以产生贡献，就交叉连边，容量为 $1$， 费用为点权。

形式化地有:

$$ V_N = V \cup V' \cup \{s,t\}\\ E = { \mid (u, v) \ \mathrm{satisfies \ the \ requirement \ above} } \\ E_N = E \cup \{ \mid u \in V\} \cup \{ \mid u' \in V'\}\\ \begin{cases} c(s, u) = 1, w(s, u) = 0\\ c(u', t) = 1, w(u', t) = 0\\ c(u, v') = 1, w(u, v') = u + v\\ c(v, u') = 1, w(v, u') = u + v\\ \end{cases} $$

建完图跑一个最大费用最大流就好了。

$\mathcal{Code}$

关于 $dij + EK$ 写法。

因为 $dij$ 无法处理负权， 可以给每个点加上势能函数 $h_u$ ，然后把 $w_{u, v}$ 替换成 $h_u - h_v + w_{u, v}$。 只要可以保证 $w_{u, v} \le h_u - h_v + w_{u, v}$ 就可以把负边干掉。 那么可以先跑一次 $\mathrm{SPFA}$，把$h_i$设成$dis_i$就可以了。

#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define pii pair<int, int>
#define con make_pair
using namespace std;
const int MAXN = 2e3 + 5;
const int MAXM = 1e4 + 5;
const int INF = 0x3f3f3f3f;

int n, m, st, ed, ans, tmp, mincost, mark[MAXN * MAXN], h[MAXN], pre[MAXN], flow[MAXN];
int tot = 1, head[MAXN], edge[MAXM], cost[MAXM], nxt[MAXM], ver[MAXM], dis[MAXN], cur[MAXN], d[MAXN];
queue<int> q;
priority_queue<pii, vector<pii>, greater<pii> > que; 
bool vis[MAXN];

void AddEdge(int u, int v, int c, int w) {
    ver[++tot] = v, edge[tot] = c, cost[tot] = w, nxt[tot] = head[u], head[u] = tot;
    ver[++tot] = u, edge[tot] = 0, cost[tot] = -w, nxt[tot] = head[v], head[v] = tot;
}  

bool spfa(int st) {

	while (!q.empty()) q.pop();
	memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= 2 * m + 2; i++) dis[i] = INF;

	dis[st] = 0, q.push(st), vis[st] = 1;

	while (!q.empty()) {
		int u = q.front(); q.pop();
		vis[u] = 0;
		for (int i = head[u]; i; i = nxt[i]) {
			int v = ver[i];
			if (!edge[i] || dis[v] <= dis[u] + cost[i]) continue;
			dis[v] = dis[u] + cost[i];
			if (!vis[v]) {
				vis[v] = 1; q.push(v);
			}
		}
	}

    for (int i = 1; i <= 2 * m + 2; i++) h[i] = dis[i];

	return (dis[ed] < INF);

}

bool dijstra(int st) {

    while (!que.empty()) que.pop();
    for (int i = 1; i <= 2 * m + 2; i++) dis[i] = INF;
	memset(vis, 0, sizeof(vis));
    memset(pre, 0, sizeof(pre));

    que.push(con(0, st)), dis[st] = 0, flow[st] = INF;

    while (!que.empty()) {
        int u = que.top().second; que.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (int i = head[u]; i; i = nxt[i]) {
            int v = ver[i];
            if (!edge[i] || dis[v] <= dis[u] + cost[i] + h[u] - h[v]) continue;
            dis[v] = dis[u] + cost[i] + h[u] - h[v]; pre[v] = i; flow[v] = min(flow[u], edge[i]);
            que.push(con(dis[v], v));
        }
    }

    return (dis[ed] < INF);

}

int gcd(int x, int y) {
    if (y == 0) return x;
    else return gcd(y, x % y);
}

bool check(int x, int y) {
    if (mark[y * y - x * x] != 0 && gcd(x, mark[y * y - x * x]) == 1) return true;
    else return false; 
}

int main() {
    
    scanf("%d %d", &n, &m);
	for (int i = 1; i <= 1000; i++) mark[i * i] = i;

    st = 2 * m + 1, ed = 2 * m + 2;
    for (int i = n; i <= m; i++) {
        AddEdge(st, i, 1, 0);
		AddEdge(i + m, ed, 1, 0);
        for (int j = i + 1; j <= m; j++) if (check(i, j)) {
			// printf("--%d %d\n", i, j);
			AddEdge(i, j + m, 1, -(i + j));
			AddEdge(j, i + m, 1, -(i + j));
        }
    }

    spfa(st);
    while (dijstra(st)) {
        
        for (int i = 1; i <= 2 * m + 2; i++) h[i] = min(h[i] + dis[i], INF);
        ans += flow[ed]; mincost += flow[ed] * h[ed];

        for (int i = ed; i != st; i = ver[pre[i] ^ 1]) {
            edge[pre[i]] -= flow[ed], edge[pre[i] ^ 1] += flow[ed];
        }

    }
	printf("%d %d\n", ans / 2, -mincost / 2);

	return 0;
}